#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Josephus Problem

@time: 2020/12/10 09:49:02
@author: hhhhhliu
"""

n = 2000  # 总数n
m = 3  # 每m个删一个
k = 2  # 最终k个幸存者

print("n: %d, m: %d k: %d" % (n, m, k))
print("===== 开始删除 =====")
quotient = 0
remainder = 0  # 初始末端剩0个
quotient_list = [quotient]  # 每轮删除的个数
remainder_list = [remainder]  # 每轮末端剩余的个数
n_list = [n]  # 每轮总数
i = 1
while True:
    if n_list[-1] == 1:
        break
    # 每轮删除者与 上轮剩余总数n_list[i-1] 和 上轮末端剩余数量remainder_list[i-1] 有关
    quotient, remainder = divmod(n_list[i-1] + remainder_list[i-1], m)  # 商quotient为本轮删除的个数，余数为本轮末端剩余数量
    new_n = n_list[i-1] - quotient  # 本轮剩余的总数=上轮总数-本轮删除的个数
    quotient_list.append(quotient)
    remainder_list.append(remainder)
    n_list.append(new_n)
    print(
        "step {}: 删除了{}个，末端剩{}个，总数还有{}个".format(
            i, quotient, remainder, new_n
        )
    )
    i += 1
print("===== 结束 =====")
print("===== 开始回溯幸存者位置 =====")
i = -1
index_list = [1]
enough = True
while True:
    print("----- step %d -----" % -i)
    print(
        "幸存者在本轮中的位置->在上一轮中的位置: {}".format(index_list),
        end=" -> "
    )
    for j in range(len(index_list)):
        q, r = divmod(index_list[j] + remainder_list[i-1] - 1, m - 1)  # 幸存者在本轮中的位置【注意是都加了末端余数的】除以(m-1)，商表示在上轮中位于被3的倍数隔开的第几段，余数表示在那一段的第几个【0开头的，所以后面要加r+1】
        index_list[j] = m * q + r + 1 - remainder_list[i-1]  # 第q段*m+r+1【记得减掉末端余数】

    print(index_list)

    if len(index_list) < k:
        enough = False

    i -= 1

    if not enough:  # 如果还不够k个幸存者
        remainder = remainder_list[i+1]
        for j in range(-remainder-1, -n_list[i]-1, -m):
            print(
                "增加第%d个幸存者，其在本轮中的位置为%d" % (
                    len(index_list)+1, n_list[i] + 1 + j
                )
            )
            index_list.append(n_list[i] + 1 + j)
            if len(index_list) >= k:
                enough = True
                break
    if -i == len(remainder_list):
        break
print("===== 结束 =====")
print("The last {} survivor's indexs (in turn):{}".format(k, index_list))
